1. Field of the Invention
The invention relates to an asynchronous transfer mode (ATM) network switch. More particularly, the invention relates to an ATM switch having cell buffers for each available bit rate (ABR) virtual connection (VC) and means for outputting cells which conforms to a minimum cell rate (MCR) for each ABR VC and which fairly allocates bandwidth to all VCs on the switch.
2. State of the Art
In ATM data transmission, cells of data conventionally comprising fifty-three bytes (forty-eight bytes carrying data and the remaining five bytes defining the cell header, the address and related information) pass through the network on a virtual connection at an agreed upon rate related to the available bandwidth and the level or service paid for. The agreed upon rate will relate not only to the steady overage flow of data, but will also limit the peak flow rates.
Over an extensive network, cells on a virtual connection can become bunched together with different cells having different delays imposed upon them at different stages, so that the cell flow on a VC then does not conform with the agreed upon rates. To prevent rates being exceeded to the detriment of other VCs in the network, the network will include, for example at the boundary between different networks, means for policing the flow. The flow policing means typically includes a "leaky bucket" device which assesses the peak and average flow rates of cells on a VC and if required either downgrades the cells' priority or discards cells.
Since policing can result in the discarding of cells which should not be discarded, it is desirable to effect "traffic shaping" to space out the cells on a VC sufficiently so as to ensure that they meet the agreed upon rates, and in particular the peak rates. A problem with traffic shaping is that it is desirable to delay the transmission of cells by variable amounts in an attempt to avoid cell loss. In practice, however, variable cell delay has been difficult to implement.
Co-owned International Application Number PCT/US96/05606 discloses an ATM switch with a traffic shaping mechanism which delays the transmission of incoming cells by varying amounts of time and which accounts for both peak and average cell flow rates. The traffic shaping mechanism broadly comprises means for determining for each cell received an onward transmission time dependent upon the time interval between the arrival of the cell and the time of arrival of the preceding cell on the same VC, buffer means for storing each new cell at an address corresponding to the onward transmission time, and means for outputting cells from the buffer means at a time corresponding to the address thereof. The traffic shaping mechanism results in cells being output at a rate which is related to the rate at which they are received which eliminates or minimizes bunching.
Different virtual connections may have different priority levels. Presently, the ATM standard provides for several different priority levels. These include "constant bit rate" (CBR) service, which is the highest priority level, two "variable bit rate" (VBR) services, and available bit rate (ABR) service, which is the lowest priority level. As traffic passes through an ATM switch, it is important to handle the cells according to their level of priority.
Co-owned International Application Number PCT/US96/15737 discloses an ATM switch which includes a plurality of slot controllers each having at least one external network link and a link to a switch fabric, the slot controllers receiving ATM cells from the network and transmitting cells to other slot controllers via the switch fabric and receiving cells from the switch fabric and transmitting cells onto the network. Each slot controller is provided with a plurality of FIFO buffers, one cell FIFO for each VC established on the switch and one arbitration FIFO for each priority level, and a FIFO controller. When a cell enters a slot controller, the cell header is examined to determine the VCI and the priority level. The slot controller examines the switch fabric to find a path for the VC, selects a VC FIFO for the VC, pushes the cell into the VC FIFO, increments a counter for the VC FIFO, and, if the VC FIFO was previously empty, writes a pointer to the arbitration FIFO for the priority level of the cell FIFO. The arbitration FIFOs are examined according to a schedule and cells are popped from VC FIFOs according to priority for exit from the slot controller. According to one disclosed embodiment, the highest priority arbitration FIFO is always examined first and none of the lower priority arbitration FIFOs are examined unless the highest priority arbitration FIFO is empty. According to another embodiment, timers are set for the lower priority arbitration FIFOs and if a timer expires for a lower priority arbitration FIFO, it is examined regardless of the contents of the highest priority arbitration FIFO. According to still another embodiment, the slot controllers are coupled to two switch fabrics and two sets of arbitration FIFOs are used, one set for each switch fabric. Prior to popping a cell from a FIFO into the switch fabric, the switch fabric is examined to determine if the path is broken and whether an alternate path exists through the second switch fabric. If an alternate path is available, the cell is not sent, but the pointer for the VC FIFO is pushed into the corresponding arbitration FIFO for the second switch fabric. The system described provides efficient handling of all priority levels, but is not specifically mindful of the needs of ABR traffic.
ABR service is intended to make the best use of any remaining available bandwidth in an ATM switch after providing for the higher priority services. ABR service is suitable for data transmission which is not time sensitive, but which may be cell loss sensitive. ABR service is generally implemented by buffering data at the ingress of an ATM switch and releasing the data from the buffer into the switch core only when some available bandwidth is not being used by a higher priority connection. Clearly, in order for this approach to function correctly without an unacceptable level of cell loss, the source of the data must transmit data at a rate ("cell rate") which does not cause the buffer to overflow.
According to presently utilized techniques, ABR service is managed through the use of special ATM cells which are known as Rm cells. Rm cells are sent from the source through the destination and return to the source with information about the congestion level in the ATM switches which form the ABR VC between the source and the destination. The source is then able to modify its transmission cell rate to avoid cell loss due to congestion. As presently implemented, Rm cells include fields for indicating the current cell rate (CCR), the minimum cell rate (MCR), and the explicit rate (ER). The CCR is the rate at which the source is presently transmitting ATM cells. The MCR is a rate which is established at the time the VC is set up and indicates the minimum rate at which the source may always transmit cells without cell loss. The ER is the new rate to which the source should adjust cell transmission due to the level of congestion in the switches which form the ABR VC. The ER is set by the switches which form the ABR VC and may be a rate which is higher than or lower than the CCR. However, the ER may not be set lower than the MCR. Various algorithms are utilized in ATM switches to set the ER for an ABR VC.
Several difficulties have been encountered with the implementation of ABR service. Many of the algorithms used to determine the ER are not equipped to deal with the situation when the calculated ER is less than the MCR. For example, most algorithms assume that all ABR VCs through the switch have the same MCR and that the ER for any ABR VC will be applied to all ABR VCs through the switch. In reality, different ABR VCs have different MCRs. If the calculated ER is lower than some of the actual MCRs of the ABR VCs through the switch, these ABR VCs will not be reduced to the calculated ER even though the algorithm assumes that they will. Thus, the algorithm will assume that congestion has been accounted for when, in reality some of the ABR VCs will continue to operate at a CCR which is too high for the congestion on the VCs.